class PriorityQueue {
    constructor(comparator) {
        this._records = [];
        this.comparator = comparator;
    }

    //堆向上调整
    _heapUpAdjust(k, record) {
        while (k > 0) {
            let parent = Math.floor((k - 1) / 2);
            let e = this._records[parent];
            if (this.comparator(e, record) <= 0) {
                break;
            }
            this._records[k] = e;
            k = parent;
        }
        this._records[k] = record;
    }

    _heapDownAdjust(k, record) {
        let half = Math.floor(this._records.length / 2);
        while (k < half) {
            let child = k * 2 + 1;
            let c = this._records[child];
            let right = child + 1;
            if (right < this._records.length && this.comparator(c, this._records[right]) > 0) {
                child = right;
                c = this._records[child];
            }
            if (this.comparator(record, c) <= 0) {
                break;
            }
            this._records[k] = c;
            k = child;
        }
        this._records[k] = record;
    }

    //销毁
    destroy() {
        this._records = null;
        this.comparator = null;
    }

    //将记录插入队列
    enQueue(record) {
        this._records.push(record);
        this._heapUpAdjust(this._records.length - 1, record);
    }

    //删除并返回队头记录
    deQueue() {
        if (this.size() === 0) {
            return null;
        }
        let record = this.peek();
        let x = this._records[this.size() - 1];
        this._records.length --;
        if (this.size() !== 0) {
            this._heapDownAdjust(0, x);
        }
        return record;
    }

    //获取队头记录
    peek() {
        return this._records[0];
    }

    //获取队列长度
    size() {
        return this._records.length;
    }

//判断队列是否为空
    isEmpty() {
        return this._records.length == 0;
    };

//清空队列
    clear() {
        this._records.length = 0;
    }

    show() {
        console.log(`this._records: ${this._records}`);
    }

}
module.exports = PriorityQueue;
